Add Two Numbers II

LeetCode 445 | Difficulty: Medium

Medium

Problem Description

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

Constraints:

- The number of nodes in each linked list is in the range `[1, 100]`.

- `0 <= Node.val <= 9`

- It is guaranteed that the list represents a number that does not have leading zeros.

Follow up: Could you solve it without reversing the input lists?

Topics: Linked List, Math, Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 192 ms)

Metric	Value
Runtime	192 ms
Memory	N/A
Date	2017-10-07

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null || l2 == null) 
            throw new ArgumentNullException("list can't be null");
        
        var s1 = PushNodesToStack(l1);
        var s2 = PushNodesToStack(l2);
        int carry = 0;
        ListNode result = null;
        while (s1.Any() && s2.Any())
        {
            int sum = s1.Pop().val+s2.Pop().val+carry;
            carry = sum/10;
            sum = sum%10;
            var temp = new ListNode(sum);
            temp.next = result;
            result = temp;
        }
        while (s1.Any())
        {
            int sum = s1.Pop().val + carry;
            carry = sum / 10;
            sum = sum % 10;
            var temp = new ListNode(sum);
            temp.next = result;
            result = temp;
        }
        while (s2.Any())
        {
            int sum = s2.Pop().val + carry;
            carry = sum / 10;
            sum = sum % 10;
            var temp = new ListNode(sum);
            temp.next = result;
            result = temp;
        }
        while (carry!=0)
        {
            int sum = carry;
            carry = sum / 10;
            sum = sum % 10;
            var temp = new ListNode(sum);
            temp.next = result;
            result = temp;
        }
        return result;
    }

    private static Stack<ListNode> PushNodesToStack(ListNode head)
    {
        Stack<ListNode> result = new Stack<ListNode>();
        while (head != null)
        {
            ListNode temp = head;
            head = head.next;
            temp.next = null;
            result.Push(temp);
        }
        return result;
    }
}

📜 1 more C# submission(s)

Submission (2017-10-07) — 199 ms, N/A

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null || l2 == null) 
            throw new ArgumentNullException("list can't be null");
        
        var s1 = PushNodesToStack(l1);
        var s2 = PushNodesToStack(l2);
        int carry = 0;
        ListNode result = null;
        while (s1.Any() && s2.Any())
        {
            int sum = s1.Pop().val+s2.Pop().val+carry;
            AddSumToResult(ref result, sum, ref carry);
        }
        while (s1.Any())
        {
            int sum = s1.Pop().val + carry;
            AddSumToResult(ref result, sum, ref carry);
        }
        while (s2.Any())
        {
            int sum = s2.Pop().val + carry;
            AddSumToResult(ref result, sum, ref carry);
        }
        while (carry!=0)
        {
            int sum = carry;
            AddSumToResult(ref result, sum, ref carry);
        }
        return result;
    }
    
    private static void AddSumToResult(ref ListNode result, int sum, ref int carry)
    {
        carry = sum / 10;
        sum = sum % 10;
        var temp = new ListNode(sum);
        temp.next = result;
        result = temp;
    }

    private static Stack<ListNode> PushNodesToStack(ListNode head)
    {
        Stack<ListNode> result = new Stack<ListNode>();
        while (head != null)
        {
            ListNode temp = head;
            head = head.next;
            temp.next = null;
            result.Push(temp);
        }
        return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?